\section{SVD, Aloha}

First, just point out some properties of SVD of order 2 tensors without proof. The derivation is quite simple. Given the SVD factorization of matrix \textbf{A}

\begin{equation}\nonumber
\textbf{A} = \textbf{U}\boldsymbol{\Sigma}\textbf{V}^T
\end{equation}

\begin{enumerate}
\item The right singular vectors corresponding to nonzero singular values span the row space of \textbf{A}.
\item The right singular vectors corresponding to zero singular values span the null space of \textbf{A}.
\item The left singular vectors corresponding to nonzero singular values span the column space of \textbf{A}.
\item The left singular vectors corresponding to zero singular values span the left null space of \textbf{A}.
\end{enumerate}

Then we start our real problem. The problem comes from ~\cite{Vasilescu:2004:TMI}. In that paper, they proposed a bound over the error of the reconstructed tensor after dimension reduction. Basically they have the following statement

\begin{equation}\nonumber
\|\mathcal{D}-\hat{\mathcal{D}}\|_{F}^2 = \sum_{i_1=R_1+1}^{\bar{R}_1}\cdots\sum_{i_N=R_N+1}^{\bar{R}_N}\mathcal{Z}_{i_1i_2\ldots i_N}^2 \leq \sum_{i_1=R_1+1}^{\bar{R}_1}\sigma_{i_1}^2 + \cdots + \sum_{i_N=R_N+1}^{\bar{R}_N}\sigma_{i_N}^2
\end{equation}

If we accept the equality, then the inequality is straightforward. As in the paper, the Frobenius norm of the subtensor $\mathcal{Z}_{i_n=m}$ equals the singular value associated with the $m^{th}$ singular vector in mode matrix $\textbf{U}_n$. To prove this, one can just show it using the SVD of tensor $\mathcal{D}$'s mode-n matrix. Then due to the overlaping of those subtensors associated with the discarded singular vectors, such inequality holds. Now let's prove why the equality also holds. First we give the N-mode SVD of the a given tensor $\mathcal{D}$ and the reconstruction of its dimension reduced version $\hat{\mathcal{D}}$.

\begin{equation}\nonumber
\begin{split}
\mathcal{D} &= \mathcal{Z} \times_1 \textbf{U}_1 \times_2 \textbf{U}_2 \cdots \times_N \textbf{U}_N\\
\hat{\mathcal{D}} &= \mathcal{Z} \times_1 \hat{\textbf{U}}_1 \times_2 \hat{\textbf{U}}_2 \cdots \times_N \hat{\textbf{U}}_N\\
\mathcal{T} &= \mathcal{D} - \hat{\mathcal{D}}
\end{split}
\end{equation}

Then back to the problem

\begin{equation}\nonumber
\begin{split}
\|\mathcal{D}-\hat{\mathcal{D}}\|_{F}^2 &= \|\mathcal{T}\|_{F}^2 = \|\mathcal{T}_{(n)}\|_{F}^2 = tr[\mathcal{T}_{(n)}^T\mathcal{T}_{(n)}] = tr[\mathcal{T}_{(n)}^T\textbf{U}_n\textbf{U}_n^T\mathcal{T}_{(n)}] \\
&= \|\textbf{U}_n^T\mathcal{T}_{(n)}\|_{F}^2 = \|\mathcal{T}_{(n)}\times_n\textbf{U}_n^T\|_{F}^2 = \|\mathcal{D}\times_n\textbf{U}_n^T-\hat{\mathcal{D}}\times_n\textbf{U}_n^T\|_{F}^2\\
&= \|\mathcal{M}\times_n\textbf{U}_n\times_n\textbf{U}_n^T-\hat{\mathcal{M}}\times_n\hat{\textbf{U}}_n\times_n\textbf{U}_n^T\|_{F}^2, (\mathcal{M} = \mathcal{D}\times_n\textbf{U}_n^T, \hat{\mathcal{M}} = \hat{\mathcal{D}}\times_n\hat{\textbf{U}}_n^T)\\
&= \|\mathcal{M}\times_n(\textbf{U}_n^T\textbf{U}_n)-\hat{\mathcal{M}}\times_n(\textbf{U}_n^T\hat{\textbf{U}}_n)\|_{F}^2 = \|\mathcal{M}\times_n\textbf{I}_n-\hat{\mathcal{M}}\times_n\hat{\textbf{I}}_n\|_{F}^2
\end{split}
\end{equation}

Here $\textbf{I}_n$ is a $\bar{R}_n \times \bar{R}_n$ identity matrix and $\hat{\textbf{I}}_n$ has the following structure

\begin{equation}\nonumber
\hat{\textbf{I}}_n = \begin{pmatrix}
i_{11} & 0 & \cdots & \cdots & \cdots & 0 & 0\\
0 & i_{22} & \cdots & \cdots & \cdots & 0 & 0\\
\vdots & \vdots & \ddots & & & \vdots & \vdots \\
\vdots & \vdots &  & i_{R_nR_n} &  & \vdots & \vdots \\
\vdots & \vdots &  & & \ddots  & \vdots & \vdots\\
0 & 0 & \cdots & \cdots & \cdots & 0 & 0\\
0 & 0 & \cdots & \cdots & \cdots & 0 & 0
\end{pmatrix}, i_{11} = i_{22} = \cdots = i_{R_nR_n} = 1
\end{equation}

As the tensor matrix product is order independent, we can apply $\textbf{U}_n^T$, n= 1, 2, $\cdots$, N one by one to $\mathcal{T}$. Finally we get to the place

\begin{equation}\nonumber
\begin{split}
\|\mathcal{D}-\hat{\mathcal{D}}\|_{F}^2 &= \|\mathcal{Z}\times_1\textbf{I}_1\times_2\textbf{I}_2\cdots\times_N\textbf{I}_N-\mathcal{Z}\times_1\hat{\textbf{I}}_1\times_2\hat{\textbf{I}}_2\cdots\times_N\hat{\textbf{I}}_N\|_{F}^2\\
&= \|\mathcal{Z}-\mathcal{Z}\times_1\hat{\textbf{I}}_1\times_2\hat{\textbf{I}}_2\cdots\times_N\hat{\textbf{I}}_N\|_{F}^2
\end{split}
\end{equation}

Notice here what $\mathcal{Z}\times_1\hat{\textbf{I}}_1\times_2\hat{\textbf{I}}_2\cdots\times_N\hat{\textbf{I}}_N$ does is simply picking out the elements $\mathcal{Z}_{i_1i_2\cdots i_N}$ when $i_1 \leq R_1, i_2 \leq R_2 \cdots i_N \leq R_N$. After the deduction, the terms left in the tensor are their complement set which is $\mathcal{Z}_{i_1i_2\cdots i_N}$ when $i_1 > R_1$ or $i_2 > R_2$ or $\cdots$ or $i_N > R_N$. Then we come to the final conclusion

\begin{equation}\nonumber
\|\mathcal{D}-\hat{\mathcal{D}}\|_{F}^2 = \|\mathcal{Z}\|_{F}^2 - \sum_{i_1=1}^{R_1}\cdots\sum_{i_N=1}^{R_N}\mathcal{Z}_{i_1i_2\ldots i_N}^2
\end{equation}

Notice here the result is different from the one in the paper even though it doesn't effect the inequality. I also tried it in Matlab and the results I got convinced me that my result is the correct one.